In order to verify and certify the origin of certain data, a system may be used in which users have public keys which must be certified in order to provide security. This type of system, a public key infrastructure (PKI), relies on certification of public keys.
In such a public key (or “asymmetric”) scheme, each user has a private key and a public key. The user can use the private key to compute a signature for a given message. Upon receipt of a signed message, the recipient can use the public key for the purported sender to determine whether the message was, indeed, signed using the sender's private key. Security is maintained because the private key can not be determined using the public key; therefore by keeping the private key private and disseminating the public key widely, the user will have the advantages of security and wide verifiability of signatures.
However, the system will not work unless it can be clearly ascertained that the public key the recipient associates with a particular sender is actually that sender's public key. For example, if a message arrives that is purportedly from Alice but is actually from an impostor, the recipient will not know that it is not from Alice if the public key that the recipient believes to be Alice's is actually one for which the impostor has the private key.
This system also works in reverse—a message may be sent to a recipient encrypted using the recipient's public key. The decryption can be accomplished only with the private key, and again, it is therefore important to ensure that the proper public key is being used, or an impostor may be able to intercept and decrypt the communication.
In order to control for this, certificates are issued (and revoked) by a authenticated data server. The authenticated data server contains certificates which are themselves signed using the public key/private key system. The certificates may be stored locally. For example, in prior art FIG. 1, a user 10, running an application 20, may provide the application with certificates, as indicated by the arrow from user 10 to application 20. The application 20 may provide that certificate to verification component (verifier) 30, as indicated by the arrow between them. The verifier 30 may also receive certificates from a local database 40. The database 40 may also receive certificates from the application 20. In order to determine whether needed certificates are available, the verifier 30 must be able to interpret a policy, received from the user 10 or application 20, which determines which certificates will be used. If the right certificates are not available locally, the user 10 must then attempt to retrieve them over network 70 from remote database 60 via the retrieval component 50. A few applications 20 may be smart enough to retrieve missing certificates without user intervention, but these are not widespread.
The problem with the prior art system is that there is duplication of two kinds: between the verifier 30 and the application 20 and between different applications 20. In order to see how there can be duplication between the verifier 30 and the application 20, suppose application 20 is an email application using the PGP system (PGP stands for “Pretty Good Privacy” and is described in P. Zimmerman, The Official PGP User's Guide, MIT Press 1995). If the email application is being used to send an encrypted message to Bob, and the policy is to “rely on either Alice or Trent for key bindings” the email application will invoke the verifier 30, which will examine the policy and look for a certificate for Bob signed by Alice or Trent in the local database 40 or for other information which could verify Bob's key (for example, a certificate signed by Alice which allows Eve to provide key bindings in her stead, and a certificate signed by Eve which can verify Bob's key.) If no such certificate is found, it reports failure to the email application. If the email application were “smart” it would examine the policy to determine what certificates are needed from remote database 60, and therefore which query to send to retrieval component 50. If email application is not this advanced, it may be left to the user 10 to request the necessary certificates. In this case, both the verifier 30 and the application 20 or user 10 are examining the policy. In the case of the smart application 20, the logic for understanding policies is duplicated in the verifier 30 and the application 20, and that it will be executed not once or even twice, but three times: once for the failed verification, a second time by the application 20 to formulate the query to the retrieval component 50 or the user, and a final time by the verifier when the application submits the retrieved certificates for approval.
Another sort of duplication exists between different applications. An application that wants to have automated certificate retrieval may not be able to use the retrieval mechanism of an existing second application. The code in the second application may be proprietary or specific to that application, or the writer of the first application may not trust the writers of the second system. Policy languages and verifiers of prior art systems (such as PolicyMaker (described in M. Blaze et al., “Decentralized Trust Management”, Proceedings of the 17th Symposium on Security and Privacy, pp. 164–173 IEEE Computer Society Press, 1996) and SPKI/SDSI (described in C. M. Ellison et al., “SPKI Certificate Theory” available at <http://ietf.org/rfc/rfc2693.txt?number=2693>)) were made as general as possible in order to eliminate this sort of duplication in policy language interpretation and verification. However, it has not been eliminated for policy-directed retrieval.
In order to provide policy-directed certificate retrieval, the prior art verifier 30 receives responses to its query from the remote database 60 over the network 70 in a format which includes the query or a hash of the query. This requires the remote database 60 and related remote system (not pictured) to be on-line (to contain a private key and encryption software) in order to provide security (signing) for the responses sent to the verifier 30. This is a clear security problem, as the remote database 60 is attached to the network 70, and therefore vulnerable to unauthorized access. Off-line signing solves the security problem, however the flexibility of the system is limited and storage needs at the remote database 60 may be increased.
Additionally, prior art retrieval devices provide revocation capabilities. This is useful in order to revoke the validity of information that has already been sent out into the distributed secure system. The prior art method of ensuring that information relied upon has not been revoked is to establish a separate protocol which is invoked in order to find out if issued certificates have been revoked. Attempts have also been made to provide revocation by providing certificates which indicate non-membership. (Described in Moni Naor and Kobbi Nissim, “Certificate Revocation and certificate update”, 7th USENIX Security Symposium, 1998.) If not used properly, this can cause security loopholes. An adversary can collect certificates and present contradictory certificates in order to overcome security restrictions. For example, if a certificate indicates that Ann is a member of the group students, and school individuals has been defined as a group consisting of the combinations of subgroups teachers, administrators and students, then Ann may be able to receive a certificate verifying that Ann is a member of the group school individuals. However, if school employees has been defined as the group consisting of those in the group school individuals who are not in the group students, and Ann graduates or leaves the school and can obtain a certificate indicating that she is no longer in the group students, then she may be able to present herself as a school employee even though she is not. To do this, she could present that certificate (“Ann is not a student”) and her earlier certificate (“Ann is a school individual”) and may qualify as a school employee, as she can show that she satisfies the definition. This is clearly a security loophole—an adversary may collect different certificates and present them in ways which allow revocation certificates to be used to overcome security restrictions.
It is clear that certificates will be used by more and more applications in the coming years. For example, consider the documents involved in pre-approval of a mortgage. Today, these documents are passed along by mail, fax, computer network, orally (over the telephone), through personal contact, and so on. The authentication of documents generally relies on letterheads and the security of communication channels like the telephone or personal meetings. The person requesting the mortgage and the one granting it would like to come to mutual agreement. This agreement involves information transfer, which could be verified by a security system. In addition to provision of security for these transactions, a system which can integrate security and the organization of the data flow and requests would be a significant improvement over the prior art.